\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  \texttt{1\ l\ r\ x}：把区间 \([l,r]\) 所有大于 \(x\) 的数减去 \(x\)
\item
  \texttt{2\ l\ r\ x}：查询区间 \([l,r]\) 内的 \(x\) 的出现次
\item
  \(1\le l\le r\le n⩽100000,1\le a_i,x\le 100000\)（弱化版，可在线）
\item
  \(1\le n\le 10^6\)，\(1\le m\le 5\times 10^5\)（强化版，因为空间不够需要离线）
\end{itemize}

\begin{lstlisting}
//在线
#include <bits/stdc++.h>
#define il inline
#define SZ 333				   //块的大小
#define L(a) ((a)*SZ - SZ + 1) //某个块左端点
#define R(a) ((a)*SZ)		   //某个块右端点
using namespace std;
struct node
{
	int rt, nm;
} g[405][110005]; //每个块内值域结构体，rt是值域对应的祖先，num是这个值出现次数
int n, Q, bl[110005], far[110005], v[110005], a[110005], mx[110005], lz[110005];
//bl是分块中的某个节点属于哪个块，a是初始的数组值，v是一个并查集节点对应的权值
//far是并查集的祖先数组，mx是区间最大值，lz是懒标记
il int find(int x)
{
	return x == far[x] ? x : far[x] = find(far[x]);
}
//并查集找祖先，自带路径压缩（
il void push(int x) //下压一个标记
{
	for (int i = L(x), e = R(x); i <= e; ++i) a[i] = v[find(i)], g[x][a[i]].rt = g[x][a[i]].nm = 0, a[i] -= lz[x];
	//遍历这个块中的所有元素，把这个块的东西塞回a中
	lz[x] = 0;
	for (int i = L(x), e = R(x); i <= e; ++i) far[i] = 0; //把这个区间清空
}
il void init(int x) //初始化一个块
{
	mx[x] = 0;
	for (int i = L(x), e = R(x); i <= e; ++i)
	{
		mx[x] = max(mx[x], a[i]), ++g[x][a[i]].nm; //记录区间最大值以及某个值域位置元素个数
		if (g[x][a[i]].rt) far[i] = g[x][a[i]].rt;
		else v[i] = a[i], g[x][a[i]].rt = far[i] = i;
		//如果这个点已经有值域节点存在了，那就直接把当前节点合并到先前节点上去
		//否则新建一个值域节点
	}
}
il void chng(int x, int a, int b) //把值域为a的位置和值域为b的合并
{
	node &s = g[x][a], &t = g[x][b]; //找到两个节点
	if (t.rt) far[s.rt] = t.rt;
	else t.rt = s.rt, v[s.rt] = b;
	t.nm += s.nm, s.nm = s.rt = 0; //直接暴力合并，并把s给删除
	//如果b不存在就直接向a贺就好了，直接把a指向b
}
il void atag(int x, int ad) //打标记
{
	if (ad <= mx[x] - lz[x] - ad)
	{
		for (int i = lz[x] + 1; i <= lz[x] + ad; ++i) if (g[x][i].rt) chng(x, i, i + ad);
		lz[x] += ad;
	}
	else
	{
		for (int i = mx[x]; i > lz[x] + ad; i--) if (g[x][i].rt) chng(x, i, i - ad);
		mx[x] = min(mx[x], lz[x] + ad);
	}
	//刚刚说的分两种情况讨论，应该还挺好懂的吧，不解释了
}
il void chang(int l, int r, int x) //区间修改操作
{
	int p = bl[l], q = bl[r];
	push(p);
	if (p ^ q) push(q); //都先下推tag
	if (p ^ q)
	{
		for (int i = l, e = R(p); i <= e; ++i) if (a[i] > x) a[i] -= x;
		for (int i = L(q); i <= r; ++i) 	   if (a[i] > x) a[i] -= x; //暴力的边块
		for (int i = p + 1; i <= q - 1; ++i)   atag(i, x);	  //整块打标记
		init(p), init(q); //再记录回去块的信息
	}
	else
	{
		for (int i = l; i <= r; ++i) if (a[i] > x) a[i] -= x;
		init(p);
	}
	//否则直接完全的暴力！
}
il int query(int l, int r, int x) //区间查询操作
{
	//只需要对于每个块来查询值域上所对应的位置出现次数即可
	int p = bl[l], q = bl[r], res = 0; //分块基本套路，和chang差不多
	if (p ^ q)
	{
		for (int i = l, e = R(p); i <= e; ++i) if (v[find(i)] - lz[p] == x) ++res;
		for (int i = L(q); i <= r; ++i) if (v[find(i)] - lz[q] == x) ++res;
		for (int i = p + 1; i <= q - 1; i++) if (x + lz[i] <= 100000) res += g[i][x + lz[i]].nm; //防止越界
	}
	else for (int i = l; i <= r; ++i) if (v[find(i)] - lz[p] == x) ++res;
	return res;
}
signed main()
{
	cin >> n >> Q;
	for (int i = 1; i <= n; i++) cin >> a[i], bl[i] = (i - 1) / SZ + 1;
	for (int i = bl[1]; i <= bl[n]; i++) init(i), lz[i] = 0;
	while (Q--)
	{
		int op, l, r, x;
		cin >> op >> l >> r >> x;
		if (op == 1)
		chang(l, r, x);
		else
		cout << query(l, r, x) << '\n';
	}
	return 0;
}
\end{lstlisting}

\begin{lstlisting}
// 离线
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define il inline
using namespace std;
char buf[1 << 22], *p1 = buf, *p2 = buf, obuf[1 << 22], *O = obuf;
int read()
{
	char c = getchar();
	int z = 0, f = 1;
	while (c != '-' && (c > '9' || c < '0'))
	c = getchar();
	if (c == '-')
	f = -1, c = getchar();
	while (c >= '0' && c <= '9')
	z = (z << 1) + (z << 3) + c - '0', c = getchar();
	return z * f;
}
const int N = 1e6 + 5, M = 1205, V = 1e5 + 5;
int tag, MV, n, m, fa[N], a[N], to[V], klen, blocks, L[M], R[M], rt[V], siz[N], ans[500005];
il int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
il void merge(int x, int y)
{
	if (rt[y]) fa[rt[x]] = rt[y];
	else rt[y] = rt[x], to[rt[y]] = y;
	siz[y] += siz[x];
	rt[x] = siz[x] = 0;
}
il void build(int o)
{
	MV = tag = 0;
	rep(i, L[o], R[o])
	{
		MV = max(MV , a[i]);
		if (rt[a[i]]) fa[i] = rt[a[i]];
		else rt[a[i]] = fa[i] = i, to[i] = a[i];
		++ siz[a[i]];
	}
}
il void modify(int x) 
{
	if ((x << 1) <= MV - tag)
	{
		rep(i, tag + 1, tag + x)
		if (rt[i]) merge(i, i + x);
		tag += x;
	}
	else
	{
		rep(i, tag + x + 1, MV)
		if (rt[i]) merge(i, i - x);
		if (MV - tag > x) MV = x + tag;
	}
}
il void restruct(int x, int l, int r, int nx)
{
	rep(i, L[x], R[x])
	a[i] = to[find(i)],
	rt[a[i]] = siz[a[i]] = 0, a[i] -= tag;
	rep(i, L[x], R[x])
	to[i] = 0;
	l = max(l, L[x]), r = min(r, R[x]);
	rep(i, l, r)
	if (a[i] > nx) a[i] -= nx;
	build(x);
}
struct que
{
	int op, l, r, x;
} q[500005];
il void ask(int x, int i)
{
	int l = q[i].l, r = q[i].r, nx = q[i].x;
	if (nx + tag > 5e5)
	return;
	if (l <= L[x] && R[x] <= r)
	ans[i] += siz[nx + tag];
	else
	{
		l = max(l , L[x]);
		r = min(r , R[x]);
		rep(j, l, r) if(to[find(j)] - tag == nx) ++ ans[i];
	}
}
signed main()
{
	n = read() , m = read();
	klen = sqrt(n);
	rep(i, 1, n) a[i] = read();
	rep(i, 1, m) 
	{
		
		q[i] = (que){read(), read(), read(), read()};
	} 
	blocks = (n - 1) / klen + 1;
	rep(i, 1, blocks) L[i] = R[i - 1] + 1,
	R[i] = i * klen , R[blocks] = n;
	rep(i, 1, blocks)
	{
		memset(rt, 0, sizeof(rt)) , memset(siz, 0, sizeof(siz));
		build(i);
		rep(j, 1, m)
		{
			if (L[i] > q[j].r || R[i] < q[j].l) continue;
			if (q[j].op == 1)
			{
				if (q[j].l <= L[i] && R[i] <= q[j].r) modify(q[j].x);
				else restruct(i, q[j].l, q[j].r, q[j].x);
			}
			else ask(i, j);
		}
	}
	rep(i, 1, m) if (q[i].op == 2) cout << ans[i] << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
